"""
This is Matteo M.'s final Project for Stanford's Code in Place 2024. 
This program find the Minimum Spanning Tree in an undirected,connected, weighted graph.
It will the visualize the path in multiple visualization tool utilizing gravis library 
and jupyter notebook.

For the sake of the presentation, the graph is randomly generated utilizing Erdős–Rényi model
and enforcing the connection. The code can be easily corrected to accept a graph from user files.

"""
import gravis as gv
import networkx as nx
import random
from itertools import combinations, groupby

# Create a graph of N nodes, with a probability of P of being connected
N = 15
P = 0.2
edges = combinations(range(N), 2)
G = nx.Graph()
G.add_nodes_from(range(N))

for _, node_edges in groupby(edges, key=lambda x: x[0]):
    node_edges = list(node_edges)
    random_edge = random.choice(node_edges)
    G.add_edge(*random_edge)
    for e in node_edges:
        if random.random() < P:
            G.add_edge(*e)
            
# Generate random weight parameter for the edges            
for (start, end) in G.edges:
    G.edges[start, end]['weight'] = random.randint(1,100)
    
#Assign graph and edges
graph_input = G    
graph_input.edges.data('weight')


# Centrality calculation
centrality = nx.algorithms.degree_centrality(graph_input)

# Community detection
communities = nx.algorithms.community.greedy_modularity_communities(graph_input)

# Assignment of node sizes
nx.set_node_attributes(graph_input, centrality, 'size')

for node in graph_input.nodes:
    graph_input.nodes[node]['color'] = 'Red'
    graph_input.nodes[node]['size'] = 10
    

# Plot the graph    
gv.three(graph_input, use_edge_size_normalization=True, edge_size_factor = 4.0)

# Find the minimum spanning tree
mst = nx.minimum_spanning_tree(G,algorithm="prim")

# Color the edge path in green 
for e in mst.edges:
    mst.edges[e]['color'] = 'green'

# Plot the Minimun Spanning Tree finded
gv.three(mst, use_edge_size_normalization=True, edge_size_factor = 4.0)

# Add the Minimum Spanning tree path in the original graph, the mst line will show ticker and colored green
for e in mst.edges:
    graph_input.edges[e]['color'] = 'green'
    graph_input.edges[e]['size'] = 1.2
    
# Plot the graph with the minimum spanning tree
gv.three(graph_input, use_edge_size_normalization = True,edge_size_factor = 0.4)

# Add a  bi-dimensional model of the graph with the mst path highlighted
gv.vis(graph_input, show_node_label = True, show_edge_label = True, 
       edge_label_data_source = 'weight',node_label_size_factor = 1.5)

Minimum Spanning Tree (MST) of a random generated connected Graph¶

1. Random connected undirected Graph Generation and visualization¶

2. Minimum Spanning Tree determination with Prim's Algorithm¶

3. Plot of the MST over the original Graph¶

4. Bi-dimensional rappresentation of the Graph¶